We destroy a finite tree of size $n$ by cutting its edges one after the otherand in uniform random order. Informally, the associated cut-tree describes thegenealogy of the connected components created by this destruction process. Weprovide a general criterion for the convergence of the rescaled cut-tree in theGromov-Prohorov topology to an interval endowed with the Euclidean distance anda certain probability measure, when the underlying tree has a small height oforder $o(\sqrt{n})$. In particular, we consider uniform random recursive trees,binary search trees, scale-free random trees and a mixture of regular trees.This yields extensions of a result in Bertoin for the cut-tree of uniformrandom recursive trees and also allows us to generalize some results of Kubaand Panholzer on the multiple isolation of vertices. The approach relies in theclose relationship between the destruction process and Bernoulli bondpercolation, which may be useful for studying the cut-tree of other classes oftrees.
展开▼
机译：我们通过依次剪裁其边缘并以统一的随机顺序销毁大小为$ n $的有限树。非正式地，关联的剪切树描述了此破坏过程创建的连接组件的族谱。当底层树的阶高为$ o（\ sqrt {n}）$时，我们为Gromov-Prohorov拓扑中的重新缩放后的割树收敛到具有欧几里德距离和一定概率测度的区间提供了一个通用准则。 。特别地，我们考虑统一随机递归树，二叉搜索树，无标度随机树和常规树的混合，这在Bertoin中扩展了均匀随机递归树的割树的结果，还使我们可以归纳一些Kubaand Panholzer对顶点的多重隔离的结果。该方法依赖于破坏过程与伯努利键渗渗之间的紧密关系，这对于研究其他类别树的割树可能有用。
展开▼
